import javax.swing.tree.TreeNode;
import java.util.*;

public class MyBinaryTree {
    // 二叉树：孩子表示法
    static class BTNode {
        public BTNode left;
        public BTNode right;
        char val;

        public BTNode(char val) {
            this.val = val;
        }
    }

    /**
     * 创建一颗测试树
     */
    public BTNode creatTree() {
        BTNode node1 = new BTNode('A');
        BTNode node2 = new BTNode('B');
        BTNode node3 = new BTNode('C');
        BTNode node4 = new BTNode('D');
        BTNode node5 = new BTNode('E');
        BTNode node6 = new BTNode('F');
        BTNode node7 = new BTNode('G');
        BTNode node8 = new BTNode('H');

        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        node5.right = node8;

        BTNode root = node1;
        return root;

    }


    /**
     * 二叉树的遍历
     *
     * @param root
     */

    //先序遍历：根->左->右
    void preOrder(BTNode root) {
        // 递归终止条件
        if (root == null) {
            return;
        }
        // 打印根
        System.out.print(root.val + " ");
        // 左子树
        preOrder(root.left);
        // 右子树
        preOrder(root.right);

    }

    //中序遍历：左->根->右
    void inOrder(BTNode root) {
        // 递归终止条件
        if (root == null) {
            return;
        }
        // 左子树
        inOrder(root.left);
        // 打印根
        System.out.print(root.val + " ");
        // 右子树
        inOrder(root.right);
    }

    //后序遍历：左->右->根
    void postOrder(BTNode root) {
        // 递归终止条件
        if (root == null) {
            return;
        }
        // 左子树
        postOrder(root.left);
        // 右子树
        postOrder(root.right);
        // 打印根
        System.out.print(root.val + " ");
    }

    /**
     * 获取树中节点的个数
     *
     * @param root
     * @return
     */

    int size(BTNode root) {
        if (root == null) {
            return 0;
        }
//        if (root!=null) {
//            return 1;
//        }
        int leftTree = size(root.left);
        int rightTree = size(root.right);
        return leftTree + rightTree + 1;

    }

    /**
     * 获取第K层节点的个数
     *
     * @param root
     * @param k
     * @return
     */
    int getKLevelNodeCount(BTNode root, int k) {
        if (root == null) {
            return 0;
        }
        if (k == 1) {
            return 1;
        }
        int leftTree = getKLevelNodeCount(root.left, k - 1);
        int rightTree = getKLevelNodeCount(root.right, k - 1);
        return leftTree + rightTree;
    }

    /**
     * 二叉树叶子的结点个数
     *
     * @param root
     * @return
     */
    int getLeafNodeCount(BTNode root) {
        // 空树
        if (root == null) {
            return 0;
        }
        // 叶子结点的条件：结点左右都为空
        if (root.left == null && root.right == null) {
            return 1;
        }
        // 左子树
        int leftTree = getLeafNodeCount(root.left);
        // 右子树
        int rightTree = getLeafNodeCount(root.right);
        // 返回子树叶子结点个数
        return leftTree + rightTree;
    }


    /**
     * 二叉树的高度
     *
     * @param root
     * @return
     */
    int getHeight(BTNode root) {
        if (root == null) {
            return 0;
        }
        int leftHight = getHeight(root.left);
        int righttHight = getHeight(root.right);
        return leftHight > righttHight ? leftHight + 1 : righttHight + 1;
    }


    /**
     * 检测值为value的元素是否存在
     *
     * @param root
     * @param val
     * @return
     */

    BTNode find(BTNode root, int val) {
        if (root == null) {
            return null;
        }
        if (root.val == val) {
            return root;
        }

        BTNode leftTree = find(root.left, val);
        if (leftTree != null) {
            return leftTree;
        }
        BTNode rightTree = find(root.right, val);
        if (rightTree != null) {
            return rightTree;
        }
        return null;
    }


    /**
     * 层序遍历
     *
     * @param root
     */
    public void levelOrder(BTNode root) {
        Queue<BTNode> queue = new LinkedList<>();
        if (root == null) {
            return;
        }
        queue.offer(root);
        while (!queue.isEmpty()) {
            BTNode cur = queue.poll();
            System.out.print(cur.val + " ");
            if (cur.left != null) {
                queue.offer(cur.left);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
            }
        }
    }

    /**
     * 方案一：判断一棵树是不是完全二叉树
     * @param root
     * @return
     */
    public boolean isCompleteTree1(BTNode root) {
        if (root == null) {
            return true;
        }
        Queue<BTNode> queue = new LinkedList<>();
        //Deque<BTNode> queue = new ArrayDeque<>();
        //运行时出现：NullPointException
        //查找资料原因：基于实现特性
        // 从名字可以看出 ArrayDeque 底层通过数组实现，为了满足可以同时在数组两端插入或删除元素的需求，
        // 该数组还必须是循环的，即循环数组（circular array），也就是说数组的任何一点都可能被看作起点或者终点。
        // ArrayDeque 是非线程安全的（not thread-safe），当多个线程同时使用的时候，需要程序员手动同步；
        // 另外，该容器不允许放入null元素。！！！原因：基于实现特性
        // LinkedList允许插入null元素
        BTNode cur =null;
        queue.offer(root);
        while(!queue.isEmpty()) {
            cur = queue.poll();
            if (cur!=null) {
                queue.offer(cur.left);
                queue.offer(cur.right);
            } else {
                break;
            }
        }
        while (!queue.isEmpty()) {
            cur = queue.poll();
            if (cur!=null) {
                return false;
            }
        }
        return true;
    }


    /**
     * 方案二：判断一棵树是不是完全二叉树
     *
     * @param root
     * @return
     */
    public boolean isCompleteTree2(BTNode root) {

        //空树一定是完全二叉树
        if (root == null)
            return true;
        //辅助队列
        Queue<BTNode> queue = new LinkedList<>();
        queue.offer(root);
        BTNode cur;
        //定义一个首次出现的标记位
        boolean notComplete = false;
        while (!queue.isEmpty()) {
            cur = queue.poll();
            //标记第一次遇到空节点
            if (cur == null) {
                notComplete = true;
                continue;
            }
            //后续访问已经遇到空节点了，说明经过了叶子
            if (notComplete)
                return false;
            queue.offer(cur.left);
            queue.offer(cur.right);
        }
        return true;

    }





//    public boolean getPath(BTNode root, BTNode node,
//                           Deque<BTNode> stack) {
//        if (root == null || node == null) return false;
//        stack.push(root);
////放完之后 要检查
//        if (root == node) return true;
//        boolean ret1 = getPath(root.left, node, stack);
//        if (ret1) return true;
//        boolean ret2 = getPath(root.right, node, stack);
//        if (ret2) return true;
//        stack.pop();
//        return false;
//    }
//
//    public BTNode lowestCommonAncestor2(BTNode root, BTNode p, BTNode q) {
////1、两个栈当中 存储好数据
//        Deque<BTNode> stack1 = new LinkedList<>();
//        getPath(root, p, stack1);
//        Deque<BTNode> stack2 = new LinkedList<>();
//        getPath(root, q, stack2);
////2、判断栈的大小
//
//        if (stack1.size() > stack2.size()) {
//            while (stack1.size() != stack2.size()) {
//                stack1.pop();
//            }
//        } else {
//            while (stack1.size() != stack2.size()) {
//                stack2.pop();
//            }
//        }
//        while (stack1.isEmpty() && stack2.isEmpty()) {
//            BTNode cur = stack1.peek();
//            if (stack1.pop().val == stack2.pop().val) {
//                return cur;
//            }
//        }
//        return null;
//    }
//
//
//    public int i = 0;
//
//    public BTNode buildTree(int[] preorder, int[] inorder) {
//        return buildTreeChild(preorder, inorder, 0, preorder.length - 1);
//    }
//
//    public BTNode buildTreeChild(int[] preorder, int[] inorder,
//                                 int inbegin, int inend) {
//        if (inbegin > inend) {
//            return null;
//        }
//        BTNode root = new BTNode(preorder[i]);
//        //找到当前根，在中序遍历的位置
//        int rootIndex = findIndex(inorder, inbegin, inend, preorder[i]);
//        i++;
//        root.left = buildTreeChild(preorder, inorder, inbegin, rootIndex - 1);
//        root.right = buildTreeChild(preorder, inorder, rootIndex + 1, inend);
//        return root;
//    }
//
//    private int findIndex(int[] inorder, int inbegin, int end, int key) {
//        for (int j = inbegin; j <= end; j++) {
//            if (inorder[j] == key) {
//                return j;
//            }
//        }
//        return -1;
//    }

    /**
     * 找到从根节点到指定节点node路径上的所有的节点，存放到栈当中
     * @param root
     * @param node
     * @param stack
     * @return
     */
//    public boolean getPath(TreeNode root, TreeNode node, Deque<TreeNode> stack) {
//        if(root == null || node == null)return false;
//        stack.push(root);
//        //放完之后 要检查
//        if(root == node) return true;
//        boolean ret1 = getPath(root.left,node,stack);
//        if(ret1) return true;
//        boolean ret2 = getPath(root.right,node,stack);
//        if(ret2) return true;
//        stack.pop();
//        return false;
//    }
//    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
//        //1、两个栈当中 存储好数据
//        Deque<TreeNode> stack1 = new LinkedList<>();
//        getPath(root,p,stack1);
//        Deque<TreeNode> stack2 = new LinkedList<>();
//        getPath(root,q,stack2);
//        //2、判断栈的大小
//        int size1 = stack1.size();
//        int size2 = stack2.size();
//        if(size1 > size2) {
//            int size = size1-size2;
//            while (size != 0) {
//                stack1.pop();
//                size--;
//            }
//        }else {
//            int size = size2-size1;
//            while (size != 0) {
//                stack2.pop();
//                size--;
//            }
//        }
//        //栈里面数据的个数 是一样的
//        while (!stack1.isEmpty() && !stack2.isEmpty()) {
//            if(stack1.peek() != stack2.peek()) {
//                stack1.pop();
//                stack2.pop();
//            }else {
//                return stack1.peek();
//            }
//        }
//        return null;
//    }


}








































